class Solution {
public:
    double findMedianSorted(vector<int>& nums1) 
    {
        int a=nums1.size();
        if(a%2)
        {  
            return nums1[(a-1)/2];
        }
        else
        {
            return (double)(nums1[a/2]+nums1[(a/2)-1])/2;
        }
    }
    int find(int a) 
    {

        if(a%2)
        {
            
            return (a-1)/2;
        }
        else
        {
            return (a/2)-1;
        }
    }
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) 
    {
        //由两个大小得知总大小得知中位数是正序第几个，然后两个vector从头开始谁小谁弹出，每删一次记一次数
        //用一个队列来维护每次删掉的和上一次删掉的，计数删到中位数的后一个开始判断是队列第一个还是两个值和除2.
        int size1=nums1.size();
        int size2=nums2.size();
        
        if(size1==0)
        {
            return findMedianSorted(nums2);
        }
        if(size2==0)
        {
            return findMedianSorted(nums1);
        }

        int len=size1+size2;
        int i=0;
        //提前算好c
        int c=find(len);
        queue<int>q1;
        double g=0;

        //谁小谁push
        while(!nums1.empty()&&!nums2.empty())
        {
            if(nums1[0]<=nums2[0])
            {
                i++;
                q1.push(nums1[0]);
                if(q1.size()>2)
                {  
                    q1.pop();
                }
                nums1.erase(nums1.begin());
            }
            else
            {
                i++;
                q1.push(nums2[0]);
                if(q1.size()>2)
                {
                    
                    q1.pop();
                }
                nums2.erase(nums2.begin());
            }
            //c是下标，所以是-1大于。然而后面的奇偶数判断用size()
            if(i-1>c)
            {
                if(len%2)
                {  
                    return q1.front();
                }
                else
                {
                    g=q1.front();
                    q1.pop();
                    g+=q1.front();
                    return (double)g/2;
                }
            }
        }
        while(!nums1.empty())
        {
            i++;
            q1.push(nums1[0]);
            if(q1.size()>2)
            {  
                q1.pop();
            }
            nums1.erase(nums1.begin());
            if(i-1>c)
            {
                if(len%2)
                {  
                    return q1.front();
                }
                else
                {
                    g=q1.front();
                    q1.pop();
                    g+=q1.front();
                    return (double)g/2;
                }
            }
        }
        while(!nums2.empty())
        {
            i++;
            q1.push(nums2[0]);
            if(q1.size()>2)
            {  
                q1.pop();
            }
            nums2.erase(nums2.begin());
            if(i-1>c)
            {
                if(len%2)
                {  
                    return q1.front();
                }
                else
                {
                    g=q1.front();
                    q1.pop();
                    g+=q1.front();
                    return (double)g/2;
                }
            }
        }
        nums1.clear();
        nums2.clear();
        return findMedianSorted(nums1);
    }
};